package one.three.fortySeven;

public class Steque<Item> {

	private Node<Item> node;
	private int n;

	private static class Node<Item> {
		private Item item;
		private Node next;

		@Override
		public String toString() {
			return "[" + item + "]";
		}
	}

	public void push(Item item) {
		if (node == null) {
			node = new Node<Item>();
			node.item = item;
		} else {
			Node<Item> newNode = new Node<Item>();
			newNode.item = item;
			newNode.next = node;
			node = newNode;
		}
		n++;
	}

	public void enqueue(Item item) {
		if (node == null) {
			node = new Node<Item>();
			node.item = item;
		} else {
			Node<Item> newNode = new Node<Item>();
			newNode.item = item;
			Node<Item> c = node;
			while (c.next != null) {
				c = c.next;
			}
			c.next = newNode;
		}
		n++;
	}

	public Item pop() {
		if (node != null) {
			Item item = node.item;
			node = node.next;
			n--;
			return item;
		} else {
			return null;
		}
	}

	public boolean isEmpty() {
		return node == null;
	}

	public Steque<Item> catenation(Steque<Item> q1, Steque<Item> q2) {
		if (q1 != null && q2 != null) {
			Item[] a1 = (Item[]) new Object[q1.n];
			Item[] a2 = (Item[]) new Object[q2.n];
			Steque<Item> r = new Steque<Item>();

			for (int i = a1.length - 1; i >= 0; i--) {
				a1[i] = q1.pop();
			}
			for (int i = a2.length - 1; i >= 0; i--) {
				a2[i] = q2.pop();
			}

			for (int i = 0; i < a1.length; i++) {
				r.push(a1[i]);
			}

			for (int i = 0; i < a2.length; i++) {
				r.push(a2[i]);
			}
			return r;
		}
		return q1 == null ? q2 : q1;
	}

	@Override
	public String toString() {
		StringBuilder s = new StringBuilder();
		Node<Item> c = node;
		while (c != null) {
			s.append("[" + c.item + "]");
			c = c.next;
		}
		return s.toString();
	}

	public static void main(String[] args) throws Exception {
		Steque<String> s1 = new Steque<String>();
		s1.push("a");
		s1.push("b");
		System.out.println(s1);
		Steque<String> s2 = new Steque<String>();
		s2.push("c");
		s2.push("d");
		System.out.println(s2);

		Steque<String> r = s1.catenation(s1, s2);
		System.out.println(r);
	}

}
